// @coding: utf8

/**
 分离数组中的奇数和偶数
 左右两个指针往中间逼近，保证左边是奇数，右边是偶数
 */

#include <iostream>
#include <vector>

void dump_vector(std::vector<int>& vec)
{
    std::cout << "dump_vector:" << std::endl;
    for (auto n : vec)
    {
        std::cout << n << ",";
    }
    std::cout << std::endl;
}

std::vector<int> training_plan(std::vector<int>& actions)
{
    //!::iter_swap(actions.begin(), actions.begin() + 1);
    auto result = actions.begin();
    auto cursor = actions.begin();
    while (cursor != actions.end())
    {
        if (*cursor % 2 == 1)
        {
            if (cursor != result)
                std::iter_swap(result++, cursor);
            else
                ++result;
        }
        cursor++;
    }
    return actions;
}

// @brief 奇数偶数分开
// 类似快排的做法，左右两个游标向中间收拢，相交的时候就能处理完成
std::vector<int> training_plan1(std::vector<int>& vec)
{
    int left = 0;
    int right = vec.size() - 1;
    while (left < right)
    {
        while((left < right) && vec[left] % 2 == 1) left++;
        while((left < right) && vec[right] % 2 == 0) right--;
        if (left < right)
            std::swap(vec[left], vec[right]);
    }
}

void test(std::vector<int>& vec)
{
    training_plan1(vec);
    dump_vector(vec);
}

int main()
{
    std::vector<int> vec{1,2,3,4,5};
    test(vec);
    std::vector<int> vec1{1,1,2,2,3,3,4,4};
    test(vec1);
    std::vector<int> vec2{4,4,1,1,2,2,3,3,4,4};
    test(vec2);

    return 0;
}